/*
回溯
连接：https://leetcode.cn/problems/sum-of-all-subset-xor-totals/description/
题目：1863. 找出所有子集的异或总和再求和




本质是全排列
方法1：选几个数字,
设计代码：
    全局变量：
        int sum;保存结果
        int path[];选择路径
    dfs函数：
       dfs(nums,pos)从哪里开始枚举
       for(i==pos;i<size;i++)
       {
        path+=nums[i];
        dfs(nums,i+1);
        path-=last;//干掉最后一个元素，复原现场
       }
    结果保存：
        进入函数，对path中的路径进行异或计算并更新sum

*/

class Solution {
public:

    int sum=0;
    vector<int> path;
    int subsetXORSum(vector<int>& nums) {
        dfs(nums,0);
        return sum;
    }
    void dfs(vector<int>& nums,int pos)
    {
        if(!path.empty())
        {
            int val=0;
            for(int i=0;i<path.size();i++)
            {
                val^=path[i];
            }
            sum+=val;
        }
        for(int i = pos;i<nums.size();i++)
        {
            path.push_back(nums[i]);
            dfs(nums,i+1);
            path.pop_back();
        }


    }
};

//方法2：
/**
 * 直接异或结果
 * 1. 递归结束条件：当前下标与数组⻓度相等，即已经越界，表⽰已经考虑到所有元素；
a. 将当前异或和添加⾄答案中，并返回；
2. 考虑将当前元素添加⾄当前状态，当前状态更新为与当前元素值的异或和，然后递归下⼀个元素；
3. 考虑不选择当前元素，当前状态不变，直接递归下⼀个元素；

*/

class Solution {
public:

    int sum=0;
    int path=0;
    int subsetXORSum(vector<int>& nums) {
        dfs(nums,0);
        return sum;
    }
    void dfs(vector<int>& nums,int pos)
    {
       sum+=path;
       for(int i=pos;i<nums.size();i++)
       {
           path^=nums[i];
           dfs(nums,i+1);
           //复原现场
           path^=nums[i];
       }

    }
};